package com.pan.alg.niuke.link;

/**
 * 描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
 * 例如： 给出的链表为 1\to 2 \to 3 \to 4 \to 5 \to NULL1→2→3→4→5→NULL, m=2,n=4m=2,n=4, 返回 1\to 4\to 3\to 2\to 5\to NULL1→4→3→2→5→NULL.
 *
 * <p>数据范围： 链表长度 0 < size \le 10000<size≤1000，0 < m \le n \le size0<m≤n≤size，链表中每个节点的值满足 |val| \le
 * 1000∣val∣≤1000 要求：时间复杂度 O(n)O(n) ，空间复杂度 O(n)O(n) 进阶：时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)
 */
public class LinkReverseBetween {

    /**
     *
     * @param head ListNode类
     * @param m int整型
     * @param n int整型
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here

        int currentIndex = 0 ;

        ListNode nodeStart =null;
        ListNode nodeEnd =null;
        ListNode nodeM = null;
        ListNode nodeN = null;

        ListNode currentNode =head;
        ListNode newHead = null;
        ListNode next = null;

        while(currentNode!=null){

            currentIndex++;

            //确定好 起点 与 终点
            if(currentIndex==m-1){

                nodeStart = currentNode;
            }else if(currentIndex==n+1){

                nodeEnd = currentNode;
            }

            if(currentIndex<m){

                currentNode=currentNode.next;
                continue;
            }

            if(currentIndex>=m&&currentIndex<=n){
                if(currentIndex==m){
                    nodeM = currentNode;
                    next = currentNode.next;
                }
                if(currentIndex==n){
                    nodeN = currentNode;
                }

                currentNode.next=newHead;
                newHead=currentNode;
                currentNode=next;
                if(currentNode!=null){
                    next=currentNode.next;
                }
            }else{

                break;
            }

        }


        if(nodeStart!=null){
            nodeStart.next=nodeN;
        }else{
            head = nodeN;
        }

        nodeM.next=nodeEnd;

        if(head.next==null){
            return newHead;
        }else{
            return head;
        }

    }

    public static void main(String[] args) {
        //
        int[] arr = {1,2,3};
        ListNode listNode = ListNodeUtil.transArr2List(arr);

        LinkReverseBetween linkReverseBetween = new LinkReverseBetween();
        ListNode listNode1 = linkReverseBetween.reverseBetween(listNode, 1, 2);
        ListNodeUtil.printListNode(listNode1);
    }
}
